package de.unibi.comet.util;

import java.util.Iterator;
import java.util.Stack;
import java.util.EmptyStackException;
import java.util.NoSuchElementException;

public class PreOrderIterator<T extends TreeNode> implements Iterator<T> {
	private Stack<Iterator<? extends TreeNode>> history;
	private T nextNode;
	private int minDepth;
	private int maxDepth;
	private int nextDepth;
	private int lastDepth;
	
	public PreOrderIterator(T node) {
		nextNode=node;
		history = new Stack<Iterator<? extends TreeNode>>();
		minDepth=-1;
		maxDepth=-1;
		nextDepth=0;
		lastDepth=-1;
	}

	/** Construct a constrained iterator which only returnes nodes
	 *  whose depth lies in [minDepth..maxDepth]. If either parameter
	 *  is -1, respective constraint is turned off. */
	public PreOrderIterator(T node, int minDepth, int maxDepth) {
		nextNode=node;
		history = new Stack<Iterator<? extends TreeNode>>();
		this.minDepth=minDepth;
		this.maxDepth=maxDepth;
		if (minDepth>0) step();
	}
	
	public boolean hasNext() {
		return nextNode!=null;
	}

	private void step() {
		while (nextNode!=null) {
			boolean depthLimitHit = ((maxDepth>=0) && (history.size()>=maxDepth)); 
			if (nextNode.hasChild() && !depthLimitHit)  {
				Iterator<? extends TreeNode> iter = nextNode.children();
				nextNode=(T)iter.next();
				history.push(iter);
			} else {
				try {
					Iterator<? extends TreeNode> iter = history.peek();
					while (!iter.hasNext()) {
						history.pop();
						iter = history.peek();
					}
					nextNode=(T)iter.next();
				} catch (EmptyStackException e) {
					// happens, if history is empty --> all nodes visited
					nextNode=null;
					return;
				}
			}
			nextDepth=history.size();
			if ((minDepth>=0) && (nextDepth<minDepth)) continue;
			if ((maxDepth>=0) && (nextDepth>maxDepth)) continue;
			return;
		}
	}
	
	public T next() {
		if (nextNode!=null) {
			lastDepth = nextDepth;
			T result = nextNode;
			step();
			return result;
		}
		else throw new NoSuchElementException();
	}

	/** Returns the depth of node last returned by next(). */
	public int getDepth() {
		return lastDepth;
	}
	
	/** Skips the subtree of last returned node. */
	public void skipSubtree() {
		if (nextDepth<=lastDepth) return;
		history.pop();
		try {
			Iterator<? extends TreeNode> iter = history.peek();
			while (!iter.hasNext()) {
				history.pop();
				iter = history.peek();
			}
			nextNode=(T)iter.next();
		} catch (EmptyStackException e) {
			// happens, if history is empty --> all nodes visited
			nextNode=null;
			return;
		}
		nextDepth=history.size();
		if (nextDepth<minDepth) step();
	}
	
	public void remove() { throw new UnsupportedOperationException(); }
}
